package com.note.feng.dataStructureAlgorithm.linked;

/**
 * 环形链表
 *  将单链表最后一个节点指向头节点，那么这个单链表就是一个环形链表。
 */
public class CircleLinkedList<E> {

    private Node head = null;
    private Node tail = null;

    public CircleLinkedList(int capacity){
        if(capacity < 1){
            throw new RuntimeException("capacity can not < 1");
        }
        for(int i = 1; i <= capacity; i++){
            Node node = new Node<>(i);
            if(i == 1){
              head = node;
              head.next = head;
              tail = head;
            }else{
                node.next = tail .next;
                tail.next = node;
                tail = node;
            }
        }
    }
    public CircleLinkedList(){
        this(5);
    }

    /**
     * 约瑟夫问题，出圈操作
     * @param startNo 从哪个数开始
     * @param countNo 数几个数
     * @param capacity 最开始有几个人/长度
     */
    public void exitCircle(int startNo, int countNo, int capacity){
        if(head == null || startNo < 1 || startNo > capacity){
            throw new RuntimeException("arr index wrong");
        }
        //找到开始位置
        for(int i = 0 ; i < startNo - 1; i++){
            head = head.next;
            tail = tail.next;
        }
        while(head != tail){
            //开始数数
            for(int i = 0 ; i < countNo - 1; i ++){
                head = head.next;
                tail = tail.next;
            }
            System.out.println(head.e + "元素出圈");
            head = head.next;
            tail.next = head;
        }
        System.out.println("最后留在圈内的元素：" + head.e);
    }

    public static void main(String[] args) {
        CircleLinkedList<Integer> circle = new CircleLinkedList<>(10);
        circle.exitCircle(1,7, 10);
    }

    private class Node<E>{
        private E e;
        private Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this.e = e;
            this.next =null;
        }
        public Node(){
            this.e = null;
            this.next = null;
        }
        public String toString(){
            return e.toString();
        }
    }
}
